

//
//  BinaryTree_secede.swift
//  SwiftyDSA
//
//  Created by Archer on 2018/8/16.
//  Copyright © 2018年 Archer. All rights reserved.
//

import Foundation

extension BinaryTree {
    
    public func sedece(_ node: Node<Element>) -> BinaryTree<Element> {
        
        let sedecedCount = node.count
        if node === _root {
            _root = nil
        } else if node.parent?.lchild === node {
            node.parent?.lchild = nil
        } else if node.parent?.rchild === node {
            node.parent?.rchild = nil
        }
        _size -= sedecedCount
        updateHeightAbove(node.parent)
        
        let newTree = BinaryTree<Element>()
        newTree._root = node
        newTree.root?.parent = nil
        newTree._size = sedecedCount
        return newTree
    }
}
